#include "list.h"
#include <stdlib.h>

static const int LSIZE = 1024;
struct _list
{
    void ***arr;
    int bound;
    int ds, dp;
    int size;
};

void _lt_inc_mem( list *_lt, int _front );

list* lt_create( )
{
    list *l = (list *)malloc( sizeof(list) );
    l->size = 0;
    l->bound = 1;
    l->arr = (void ***)malloc( sizeof(void**) * 2 );
    l->arr[0] = (void **)malloc( sizeof(void*) * LSIZE );
    l->arr[1] = (void **)malloc( sizeof(void*) * LSIZE );
    l->ds = 1;
    l->dp = 0;
    return l;
}

void lt_destroy( list* _lt )
{
    int i;
    for( i = 0; i < _lt->bound; ++i )
        free( _lt->arr[i] );
    free( _lt->arr );
    free( _lt );
}

int32 lt_size( list* _lt )
{
    return _lt->size;
}

void lt_pushb( list* _lt, void* _val )
{
    ++_lt->size;
    if( _lt->ds + (_lt->size-1+_lt->dp)/LSIZE > _lt->bound )
        _lt_inc_mem( _lt, 0 );
    lt_update( _lt, _lt->size-1, _val );
}

void lt_pushf( list *_lt, void *_val )
{
    ++_lt->size;
    --_lt->dp;
    if( _lt->dp < 0 )
    {
        --_lt->ds;
        _lt->dp = LSIZE-1;
    }
    if( _lt->ds < 0 )
    {
        _lt_inc_mem( _lt, 1 );
        ++_lt->ds;
    }
    _lt->arr[_lt->ds][_lt->dp] = _val;
}

void* lt_front( list *_lt )
{
    if( _lt->size > 0 )
        return _lt->arr[_lt->ds][_lt->dp];
    else
        return NULL;
}

void* lt_back( list *_lt )
{
    if( _lt->size > 0 )
        return _lt->arr[_lt->ds+(_lt->dp+_lt->size-1)/LSIZE][(_lt->dp+_lt->size-1)%LSIZE];
    else
        return NULL;
}

void* lt_popf( list* _lt )
{
    void *val = lt_front( _lt );
    if( _lt->size > 0 )
    {
        --_lt->size;
        ++_lt->dp;
        if( _lt->dp == LSIZE )
        {
            _lt->dp = 0;
            ++_lt->ds;
        }
    }
    return val;
}

void* lt_popb( list *_lt )
{
    void *val = lt_back( _lt );
    if( _lt->size > 0 )
        --_lt->size;
    return val;
}

void* lt_get( list *_lt, int _p )
{
    if( _p >= 0 && _p < _lt->size )
        return _lt->arr[_lt->ds+(_lt->dp+_p)/LSIZE][(_lt->dp+_p)%LSIZE];
    else
        return NULL;
}

void* lt_update( list *_lt, int _p, void *_val )
{
    if( _p >= 0 && _p < _lt->size )
    {
        void *val = lt_get( _lt, _p );
        _lt->arr[_lt->ds+(_lt->dp+_p)/LSIZE][(_lt->dp+_p)%LSIZE] = _val;
        return val;
    }
    else
    {
        return NULL;
    }
}

void _lt_inc_mem( list *_lt, int _front )
{
    int i;
    ++_lt->bound;
    _lt->arr = (void***)realloc( _lt->arr, sizeof(void**) * (_lt->bound+1) );
    i = _lt->bound;
    if( _front == 1 )
    {
        for( i = _lt->bound; i > 0; --i )
            _lt->arr[i] = _lt->arr[i-1];
    }
    _lt->arr[i] = (void**)malloc( sizeof(void*) * LSIZE );
}

int lt_merge( list *_lt1, list *_lt2 )
{
    int i;
    for( i = 0; i < lt_size( _lt2 ); ++i )
        lt_pushb( _lt1, lt_get( _lt2, i ) );
    return lt_size( _lt1 );
}
